package com.剑指offer.no07;

import java.util.ArrayList;


// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}


/*
 * 特性A，对于前序遍历，第一个肯定是根节点；
 * 特性B，对于后序遍历，最后一个肯定是根节点；
 * 特性C，利用前序或后序遍历，确定根节点，在中序遍历中，根节点的两边就可以分出左子树和右子树；
 * 特性D，对左子树和右子树分别做前面3点的分析和拆分，相当于做递归，我们就可以重建出完整的二叉树；
 */
public class Solution01 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 && inorder.length == 0) {
            return null;
        }

        // TODO: 定义根节点 从根左右的前序遍历中获得根节点
        TreeNode root = new TreeNode(preorder[0]);


        // TODO: 左右子树 中序遍历
        ArrayList<Integer> leftInorder = new ArrayList<Integer>();
        ArrayList<Integer> rightInorder = new ArrayList<Integer>();

        // TODO: 左右子树 前序遍历
        ArrayList<Integer> leftPreorder = new ArrayList<Integer>();
        ArrayList<Integer> rightPreorder = new ArrayList<Integer>();


        // TODO: 划分左右子树, 获得左右子树的中序遍历序列
        int rootInordex = 0;

        for (int i = 0; i <= inorder.length - 1; i++) {
            if (inorder[i] == root.val) {
                rootInordex = i;
                continue;
            }

            if (rootInordex == 0) {
                leftInorder.add(inorder[i]);
            } else {
                rightInorder.add(inorder[i]);
            }
        }

//        // TODO: 左右子树前序遍历数组
//        int[] leftPreorderArray = new int[leftPreorder.size()];
//        int[] rightPreorderArray = new int[rightPreorder.size()];
//
//        // TODO: 左右子树中序遍历数组
//        int[] leftInorderArray = new int[leftInorder.size()];
//        int[] rightInorderArray = new int[rightInorder.size()];


        // TODO: 左右子树  获得  前序遍历和中序遍历  递归
        root.left = buildTree(
                arrayListToArray(leftPreorder),
                arrayListToArray(leftInorder)
        );

        root.right = buildTree(
                arrayListToArray(rightPreorder),
                arrayListToArray(rightInorder)
        );

        return root;
    }

    private int[] arrayListToArray(ArrayList<Integer> targetList) {
        int[] resultArray = new int[targetList.size()];
        for (int i = 0; i <= targetList.size() - 1; i++) {
            resultArray[i] = targetList.get(i);
        }
        return resultArray;
    }

    public static void main(String[] args) {
        int[] test01 = {3,9,20,15,7};
        int[] test02 = {9,3,15,20,7};

        Solution01 solution = new Solution01();
        TreeNode result = solution.buildTree(test01, test02);
        System.out.print(result.val);
    }

}